package leetcode.L25;

class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        //k个翻转
        if (head==null) {
            return null;
        }
        //dummy节点
        ListNode dummy = new ListNode(0, head);
        ListNode dummyKHead = dummy;
        ListNode dummyKTail = dummy;
        int countK = 0;
        //先遍历K个长度，判断是否要逆转
        while (dummyKTail.next!=null) {
            dummyKTail = dummyKTail.next;
            countK++;
            if (countK==k) {
                //翻转k链表
                dummyKHead = reverseK(dummyKHead,k);
                //重新计数
                countK = 0;
                dummyKTail=dummyKHead;
            }
        }
        return dummy.next;
    }

    //返回尾部节点作为新的dummyKHead
    public ListNode reverseK(ListNode dummyKHead,int k) {
        ListNode tail = dummyKHead.next;
        ListNode first = tail;
        int tmp = 1;
        while (tail.next != null && tmp < k) {
            first = tail.next;
            tail.next = first.next;
            first.next = dummyKHead.next;
            dummyKHead.next = first;
            tmp++;
        }
        return tail;
    }

    public static void main(String[] args) {
        ListNode s5 = new ListNode(5, null);
        ListNode s4 = new ListNode(4, s5);
        ListNode s3 = new ListNode(3, s4);
        ListNode s2 = new ListNode(2, s3);
        ListNode s1 = new ListNode(1, s2);
        Solution solution = new Solution();
        solution.reverseKGroup(s1, 3);
    }
}